import java.util.Stack;

public class Test{
    class BinaryTree{
        int value;
        BinaryTree leftChild;
        BinaryTree rightChild;
        public BinaryTree(int val){
            this.value = val;
        }


    }
    public BinaryTree root;
    public void createTree(){
        BinaryTree A  = new BinaryTree(5);
        BinaryTree B =  new BinaryTree(3);
        BinaryTree C = new BinaryTree(7);
        BinaryTree D = new BinaryTree(1);
        BinaryTree E = new BinaryTree(4);
        BinaryTree F = new BinaryTree(6);
        BinaryTree G = new BinaryTree(8);
        BinaryTree H = new BinaryTree(0);
        BinaryTree I = new BinaryTree(2);
        BinaryTree J = new BinaryTree(9);
        root=A;
        A.leftChild = B;
        A.rightChild =C;
        B.leftChild = D;
        B.rightChild = E;
        C.leftChild = F;
        C.rightChild = G;
        D.leftChild = H;
        D.rightChild=I;
        G.rightChild = J;

    }

    public int find(int val){
        if(root==null){
            return -1;
        }
        BinaryTree cur = root;
        while(cur!=null){
            if(cur.value<val){
                cur=cur.rightChild;
            }else if(cur.value>val){
                cur=cur.leftChild;
            }else{
                return 1;
            }
        }
        return -1;
    }
    public void prior(BinaryTree root){

        Stack<BinaryTree> stack1 = new Stack<>();
        BinaryTree cur = root;
        while(cur!=null||!stack1.empty()){
            while(cur!=null){
                System.out.print(cur.value+" ");
                stack1.push(cur);
                cur=cur.leftChild;
            }
            BinaryTree tmp = stack1.pop();
            cur = tmp.rightChild;
        }

    }
    public void center(BinaryTree root){
        if(root==null){
            return ;
        }
        BinaryTree cur = root;
        Stack<BinaryTree> stack = new Stack<>();
        while(cur!=null||!stack.empty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.leftChild;
            }
            BinaryTree tmp = stack.pop();
            System.out.print(tmp.value+" ");
            cur=tmp.rightChild;
        }
    }

    public void insert(int val){
        BinaryTree newNode  =  new BinaryTree(val);
        if(root==null){
            root = newNode;
        }
        BinaryTree cur = root;
        BinaryTree parent =null;
        while(cur!=null){
            if(cur.value<val){
                parent = cur;
                cur=cur.rightChild;
            }else if(cur.value>val){
                parent = cur;
                cur=cur.leftChild;
            }else{
                System.out.println("二叉搜索树中已经存在本结点，无需插入");return;
            }
        }
        if(val< parent.value){
            parent.leftChild=newNode;
        }else{
            parent.rightChild = newNode;
        }
    }
    public void later(){
        if(root==null){
            return;
        }
        BinaryTree tmp1=null;
        BinaryTree cur = root;
        Stack<BinaryTree> stack = new Stack<>();
        while(cur!=null||!stack.empty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.leftChild;
            }

            BinaryTree tmp = stack.peek();
            if(tmp.rightChild==null||tmp.rightChild==tmp1){
               tmp1 = stack.pop();
                System.out.print(tmp.value+" ");
            }else{
                 cur=tmp.rightChild;
            }
        }
    }
    public void remove(int val){

        if(root==null){
            return;
        }
        BinaryTree cur = root;
        BinaryTree parent = null;
        while(cur!=null){
            if(cur.value<val){
                parent = cur;
                cur=cur.rightChild;
            }else if(cur.value>val){
                parent = cur;
                cur=cur.leftChild;
            }else{
                   if(parent.leftChild==cur){
                       if(cur.leftChild==null&&cur.rightChild==null){
                           parent.leftChild=null;
                           return;
                       }else if(cur.leftChild==null&&cur.rightChild!=null){
                           parent.leftChild=cur.rightChild;
                           return;
                       }else if(cur.leftChild!=null&&cur.rightChild==null){
                           parent.leftChild=cur.leftChild;
                           return;
                       }else{
                          BinaryTree tmp = cur;
                          BinaryTree tmp1=cur.leftChild;
                          tmp=cur.rightChild;
                          if(tmp.leftChild==null){
                              cur=tmp;
                              cur.leftChild=tmp1;
                              parent.leftChild=cur;
                          }else{
                              BinaryTree parentmp=null;
                              while(tmp.leftChild!=null){
                                  parentmp=tmp;
                                  tmp=tmp.leftChild;
                              }
                              cur.value=tmp.value;
                              cur.leftChild=tmp1;
                              parentmp.leftChild=null;
                          }
                       }
                   }

               else if(parent.rightChild==cur){
                    if(cur.leftChild==null&&cur.rightChild==null){
                        parent.rightChild=null;
                        return;
                    }else if(cur.leftChild==null&&cur.rightChild!=null){
                        parent.rightChild=cur.rightChild;
                        return;
                    }else if(cur.leftChild!=null&&cur.rightChild==null){
                        parent.rightChild=cur.leftChild;
                        return;
                    }else{
                        BinaryTree tmp = cur;
                        BinaryTree tmp1=cur.leftChild;
                        tmp=cur.rightChild;
                        if(tmp.leftChild==null){
                            cur=tmp;
                            cur.leftChild=tmp1;
                            parent.rightChild=cur;
                        }else{
                            BinaryTree parentmp=null;
                            while(tmp.leftChild!=null){
                                parentmp=tmp;
                                tmp=tmp.leftChild;
                            }
                            cur.value=tmp.value;
                            cur.leftChild=tmp1;
                            parentmp.leftChild=null;
                        }
                    }
                }
            }
        }
    }
    public static void main(String[] args) {
          Test test = new Test();
          test.createTree();
         /* test.prior(test.root);

          */
        System.out.println(test.find(12));



        test.later();
    }
}
